The present invention relates in general to computer animation techniques. More particularly, the invention provides a method and system for multiresolution geometry caching based on ray differentials. Merely by way of example, the invention is described as it applies to a ray tracing process, but it should be recognized that the invention has a broader range of applicability.
Throughout the years, movie makers have often tried to tell stories involving make-believe creatures, far away places, and fantastic things. To do so, they have often relied on animation techniques to bring the make-believe to “life.” Two of the major paths in animation have traditionally included drawing-based animation techniques and stop motion animation techniques.
Drawing-based animation techniques were refined in the twentieth century, by movie makers such as Walt Disney and used in movies such as “Snow White and the Seven Dwarfs” (1937) and “Fantasia” (1940). This animation technique typically required artists to hand-draw or paint animated images onto transparent media or cels. After painting, each cel would then be captured or recorded onto film as one or more frames in a movie.
Stop motion-based animation techniques typically required the construction of miniature sets, props, and characters. The filmmakers would construct the sets, add props, and position the miniature characters in a pose. After the animator was happy with how everything was arranged, one or more frames of film would be taken of that specific arrangement. Stop motion animation techniques were developed by movie makers such as Willis O'Brien for movies such as “King Kong” (1933). Subsequently, these techniques were refined by animators such as Ray Harryhausen for movies including “Mighty Joe Young” (1948) and “Clash Of The Titans” (1981).
With the wide-spread availability of computers in the later part of the twentieth century, animators began to rely upon computers to assist in the animation process. This included using computers to facilitate drawing-based animation, for example, by painting images, by generating in-between images (“tweening”), and the like. This also included using computers to augment stop motion animation techniques. For example, physical models could be represented by virtual models in computer memory, and manipulated.
One of the pioneering companies in the computer graphics (CG) industry was Pixar. Pixar developed both computing platforms specially designed for CG, and rendering software now known as RenderMan®. RenderMan® was particularly well received in the CG industry and recognized with two Academy Awards®. RenderMan® software is used to convert graphical specifications of objects and convert them into one or more images. This technique is known generally in the industry as rendering.
Pixar pioneered techniques of scanline rendering to render complex scenes. With scanline rendering, geometric complexity is reduced by dividing a scene into separate tiles and by rendering one image tile at a time. As a result, only visible objects within a tile are tessellated. To account for reflection and refraction effects, reflection and refraction maps are used. Using scanline techniques, color bleeding effects of global illumination are simulated by laboriously placing colored light sources in the scene. These lights are sometimes called “bounce lights.” The addition of ray tracing techniques to scanline rendering techniques is straightforward as long as the rays intersect geometry in a coherent fashion. Such rays are often called coherent rays. Specular reflection and refraction rays from flat or slightly curved surfaces are usually coherent rays. Furthermore, shadow rays from point lights, spot lights, directional lights, and small area lights are typically also coherent rays. Accordingly, it has been possible to combine ray tracing and scanline rendering.
For general path tracing, there is often much less geometric coherency than for classic ray tracing. This obstacle may be overcome by reordering rays. Unshot rays may be inserted into a pool of rays. For example, the image contribution of each ray is computed before the ray is inserted in the pool, and this weight as well as the ultimate pixel position of the ray color is stored with the pending ray. When sufficiently many rays are waiting to be intersection tested against an object, the geometry is read in, tessellated if not already in tessellated form, and inserted into the cache. This way, scenes can be rendered that are ten times larger than the geometry cache.
One common method to speed up rendering is to simplify geometry that only covers a small part of the image. For example, a coarse geometry representation is used for computing an approximate radiosity solution. Clusters of complex geometry can be substituted by boxes with similar reflective and transmissive properties. During rendering, rays for computing diffuse interreflection are intersected with the original geometry near the ray origins and with the boxes further away. A user-defined distance threshold can be used to switch between the two representations. Additionally, clustered geometry can be used for efficient light transport between distant groups of objects. Instead of computing light transport between all pairs of objects, the far-field radiance of one cluster of objects is computed, the light is transported to the other cluster, and then “pushed down” to its individual surfaces.
Some research has also been performed to speed up direct ray tracing without tessellation. For example, only the high-level description of the objects and a spatial acceleration data structure need to fit in memory. The high-level description may include the control points of NURBS patches or top-level subdivision meshes. These methods appear suitable for ray tracing of complex scenes, at least from a memory usage standpoint.
Additionally, certain conventional ray tracers use parallel ray tracing techniques. For example, many processors can be used on a shared memory computer to obtain interactive frame rates. For good performance, scenes need to fit in the rather small on-chip cache on each processor. In another example, a cluster of PCs is used for interactive ray tracing of complex scenes up to 50 million triangles. Ray coherency ensures that each PC only needs parts of the scene. In simpler scenes, indirect illumination can also be rendered. For example, 20–25 shadow rays per pixel are shot to virtual point lights generated by random walks, and indirect illumination is averaged between neighbor pixels to reduce noise. In yet another example, complex scenes can be handled by dividing the objects between a cluster of PCs. Each surface is tessellated and assigned to a processor. Packets of rays to be tested for intersection are communicated between the processors. After all rays have been shot by a shader, the shader is inserted into a pool of suspended shaders. When all those rays have been traced and shaded, the shader is taken out of the pool and its computation continues.
Moreover, some conventional ray tracers use ray differential techniques. Beam tracing, cone tracing, and pencil tracing trace bundles of light paths instead of infinitely thin rays. General intersection, reflection, and refraction calculations may be difficult since each bounce can split the light beam, light cone, or light pencil. As an improvement, a ray differential method traces single rays, but keeps track of the difference between each ray and two real or imaginary “neighbor” rays. These differences give an indication of the cone or beam size that each ray represents. The curvature at ray-surface intersection points determines how those ray differentials are propagated at specular reflection and refraction. For example, if a ray hits a highly curved, convex surface, the specularly reflected ray may have a large differential, which represents highly diverging neighbor rays. Ray differentials can help in texture antialiasing since they may indicate the best texture filter size, but they often do not help in aliasing of ray hits in terms of visibility: the ray either hits an object or not.
The ray differentials may be generalized for glossy and diffuse reflections. For example, the ray differential corresponds to a fraction of the hemisphere for distribution ray tracing of diffuse reflection. The more rays are traced from the same point, the smaller the fraction becomes. For path tracing of diffuse reflection, the “path differential” is a global value
      N          2      ⁢      d        ,where d is the ray depth and N is the total number of rays that reach that depth. Distribution ray tracing usually gives smaller, more accurate ray differentials than path tracing.
Conventional ray tracing techniques have limited ability to efficiently compute ray tracing and global illumination in very complex scenes. Hence it is highly desirable to improve techniques for ray tracing.